This invention relates generally to cache-based computer systems, and more particularly to a set associative cache which functions effectively in the presence of repeatable defects.
The main memory of a computer system is generally accessed in a logical order and often in a sequential fashion. Typical examples include the processing of array structures and the sequencing of instructions in executing a particular program. Alternatively, a program may repeatedly execute an instruction loop prior to transferring control to a localized area. In both of these cases, a substantial increase in the execution speed of the individual processes, and consequently the overall computer system, can be achieved if a fast auxiliary memory is provided which is capable of retaining sufficient data to avoid repeated references to the slower system memory; caches associated with system memory provide this function.
Cache memories are commonly used in high-performance computer systems in order to optimize the ratio of system memory to processor speed. Typically implemented in the form of small, high-speed buffer memories, caches continually obtain and temporarily retain data that associated system processors are likely to require in executing current operations. This data is usually in the form of a block of memory which includes the most recently used instructions and data items.
The operation of such cache memory schemes is based upon the phenomenon of locality exhibited by programs in the generation of addresses and memory usage. A program with a high degree of locality does not refer to many widely scattered memory locations in a short period of time. Therefore, cache memories essentially provide a "window" into the system memory for associated processors and permit high-speed access to data references with both spatial and temporal locality.
In typical cache implementations, the cache memory resides between a processor and the system memory, which is often referred to as the primary or main memory. Memory addresses are interpreted by using an associative memory map which defines a correspondence between address locations requested by the processor and the cache contents. If a requested data item exists within the cache, requests to main memory are inhibited by the associative memory and the desired data is supplied from the cache to the requesting processor. The system memory is accessed only when a requested data item is not located within the cache. In such a case, the required data is fetched from the system memory and then supplied to the requesting processor. In addition to fetching the requested data, the cache typically fetches several bytes of data in the vicinity of the requested data in anticipation that the processor will attempt to access the next sequential series of bytes.
Cache memories for use with high speed computer systems are fabricated on VLSI chips, and the cache memories are usually fabricated on the microprocessor chips to provide optimum access times. However, as the device density on VLSI chips increases, device defects per unit area increase. Since on-chip cache assumes an increasingly greater proportion of the chip area, defects within the on-chip cache increase. Steps must be taken to bypass the defects so that a high percentage of the cache is usable otherwise the entire chip must be scrapped. Since VLSI chips with a small number of defects form a large proportion of the scrapped yield, rendering chips with a small number of defects usable greatly increases the production yield and reduces the cost of each chip.
One popular technique for bypassing defects within on-chip cache is fabricating memory arrays having redundant rows and/or columns. After manufacture and before a chip can be shipped, each memory on the chip is tested for defects. Any defects are corrected by substituting a defective row or column with a redundant row or column. This substitution is done by destroying fusible links which interconnect the memory elements with a laser or with a PROM-like programming method. However, this technique for correcting defects within a cache has drawbacks. First, more silicon area is required for each cache memory because of the redundant rows and columns, and, secondly, errors must be detected and corrected at the time of manufacture.
Another common technique uses software diagnostic routines which test for proper cache operation. These routines transfer information from the system memory to the cache. The information is then read from the cache and compared with known information. If the comparison does not produce a "hit", i.e., if the compared information is not identical, then the software routine degrades the cache level so that it cannot be accessed.
Other common techniques include interfacing software- controlled testing apparatus to logic which disables an entire memory level if any entry in that level is defective. Techniques of this type can be used to detect errors in controller portions of the cache in addition to errors in the cache memory. The testing apparatus typically responds to certain commands which enable the cache system to signal when the data requested from cache is not stored in cache after the cache has been initialized. If a defect is detected by the apparatus or the central processing unit (CPU), the entire cache, or at least the defective cache memory level, is bypassed. By way of example, a 4-level set associative cache has 4096 words of storage which are organized into 4 rows by 1024 columns. Therefore, using a testing apparatus of this type, an entire level, i.e., one-fourth of the available cache, would be disabled if a single defect is found.
The present invention is directed to overcoming one or more of the problems as set forth above.